/*
 * @lc app=leetcode.cn id=560 lang=typescript
 *
 * [560] 和为 K 的子数组
 */

// @lc code=start

//  思路：前缀和 + 哈希表
//  参考：https://labuladong.github.io/algo/2/19/48/

//  复杂度：O(n) O(n)

function subarraySum(nums: number[], k: number): number {
    // 前缀和 --> 前缀和出现的次数
    const preSum: Map<number, number> = new Map()
    // base case
    preSum.set(0, 1)

    let res = 0, sum0_i = 0
    for (let i = 0; i < nums.length; i++) {
        sum0_i += nums[i]
        // 这是我们想找的前缀和 nums[0..j]
        const sum0_j = sum0_i - k
        // 如果前面有这个前缀和，则直接更新答案
        if (preSum.has(sum0_j)) {
            res += preSum.get(sum0_j)!
        }
        // 把前缀和 nums[0..i] 加入并记录出现次数
        preSum.set(sum0_i, (preSum.has(sum0_i) ? preSum.get(sum0_i)! : 0) + 1)
    }
    return res
};
// @lc code=end

console.log(subarraySum([1, 1, 1], 2))
console.log(subarraySum([1, 2, 3], 3))
console.log(subarraySum([1, -1, 0], 0))
console.log(subarraySum([3, 5, 2, -2, 4, 1], 5))
